#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

int N = 100;                //数据规模
int repeat = 100;     //重复次数
clock_t start, finish;
double*a,**b;
double*sum;
void init(){
    a=new double[N];
    b=new double*[N];
    sum=new double[N];
    //初始化数据
    for (int i = 0;i < N;i++){
            a[i]=i;
            b[i]=new double[N];
        for (int j = 0;j < N;j++)
            b[i][j] = i + j;
    }
}
void clc(){
for(int i=0;i<N;i++)
delete []b[i];
delete []b;
delete []a;
delete []sum;
}

int main()
{
    while(N<=5000){
    init();
    if(N%1000==0){
    if(N==1000)repeat-=15;
    if(N==2000)repeat-=20;
    if(N==3000)repeat-=25;
    if(N==4000)repeat-=30;
    }
    cout<<"Scale is"<<N<<"时："<<endl;
    //ordinary算法的时间
    start = clock();
    for (int i = 0;i < repeat;i++) {
        for (int j = 0;j < N;j++) {
            sum[j] = 0.0;
            for (int i = 0; i < N; i++)
                sum[j] += b[i][j] * a[i];
        }
    }
    finish = clock();
    cout <<"ordinary time: "<< ((double)(finish - start) / CLOCKS_PER_SEC)/repeat << endl;
    double x1 = (double)finish - start;

    //cache算法的时间
    start = clock();
    for (int i = 0;i < repeat;i++) {
        for (int i = 0;i < N;i++)
            sum[i] = 0.0;
        for (int i = 0; i < N; i++)
            for (int j = 0;j < N;j++)
                sum[j] += b[i][j] * a[i];

    }
    finish = clock();
    cout <<"cache time："<< ((double)(finish - start) / CLOCKS_PER_SEC)/repeat << endl;
    double x2 = (double)finish - start;
    cout <<"Speedup ratio："<< x1 / x2 << endl;
    cout<<endl;
    clc();
    N+=100;
    }
    return 0;
}
